/*
    随机选择算法

    前置知识：讲解023-随机快速排序

    无序数组中寻找第K大的数
    给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

    利用改写快排的方法，时间复杂度O(n)，额外空间复杂度O(1)
    上面问题的解法就是随机选择算法，是常考内容！本视频定性讲述，定量证明略，算法导论-9.2有详细证明
    不要慌！
    随机快速排序、随机选择算法，时间复杂度的证明理解起来很困难，只需记住结论，但并不会对后续的算法学习造成什么影响
    因为数学很好才能理解的算法和数据结构其实比较少，绝大部分的内容都只需要高中数学的基础就能理解

    算法导论第9章，还有一个BFPRT算法，不用随机选择一个数的方式，也能做到时间复杂度O(n)，额外空间复杂度O(log n)
    早些年我还讲这个算法，不过真的很冷门，很少在笔试、面试、比赛场合出现，所以算了。有兴趣的同学可以研究一下

*/